package main

import (
	"fmt"
	"math"
)

// 如何求数组连续最大和
// 引申：在知道子数组最大值后，如何才能确定最大子数组的位置

func main() {
	arr := []int{1, -2, 4, 8, -4, 7, -1, -5}
	fmt.Println(maxSubArray(arr))
	fmt.Println(maxSubArraySum(arr))
	fmt.Println(maxSubArrayDyn(arr))
	fmt.Println(maxSubArrayDyn2(arr))
	fmt.Println(maxSubArrayEx(arr))
}

// 蛮力法
func maxSubArray(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return math.MinInt64
	}
	maxSum := 0
	length := len(arr)

	for i := 0; i < length; i++ {
		for j := i; j < length; j++ {
			sum := 0
			for k := i; k <= j; k++ {
				sum += arr[k]
			}
			if sum > maxSum {
				maxSum = sum
			}
		}
	}

	return maxSum
}

// 重复利用已经计算的子数组和
func maxSubArraySum(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return math.MinInt64
	}

	length := len(arr)
	maxSum := math.MinInt64
	var sum int

	for i := 0; i < length; i++ {
		sum = 0
		for j := i; j < length; j++ {
			sum += arr[j]
			if sum > maxSum {
				maxSum = sum
			}
		}
	}

	return maxSum
}

// 动态规划方法
func maxSubArrayDyn(arr []int) int {
	if arr == nil || len(arr) == 0 {
		return math.MinInt64
	}

	l := len(arr)

	end := make([]int, l) // 每个元素代表以当前节点结尾的连续最大和
	all := make([]int, l) // 每个元素代表以当前或之前的任意节点结尾的连续最大和

	end[0], end[l-1] = arr[0], arr[l-1]
	all[0], all[l-1] = arr[0], arr[l-1]

	for i := 1; i < l; i++ {
		end[i] = max(end[i-1]+arr[i], arr[i])
		all[i] = max(end[i], all[i-1])
	}

	return all[l-1]
}

// 动态规划法优化
func maxSubArrayDyn2(arr []int) int {
	if arr == nil || len(arr) < 1 {
		return -1
	}

	nAll := arr[0]
	nEnd := arr[0]

	for _, v := range arr {
		nEnd = max(nEnd+v, v)
		nAll = max(nEnd, nAll)
	}

	return nAll
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func maxSubArrayEx(arr []int) (maxSum, begin, end int) {
	maxSum = math.MinInt64
	nSum := 0
	nStart := 0

	for i, v := range arr {
		if nSum < 0 {
			nSum = v
			nStart = i
		} else {
			nSum += v
		}
		if nSum > maxSum {
			maxSum = nSum
			begin = nStart
			end = i
		}
	}

	return
}
